package com.wtgroup.demo.mianshi.算法;

import cn.hutool.core.lang.Assert;
import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Sout;
import com.wtgroup.demo.common.util.Tools;

/**
 * 红白蓝，荷兰国旗，红 小于，白 等于，蓝 大于
 *
 * @author nisus
 * @version 0.1
 * @since 2023/5/2 17:13
 */
public class Q_数组三色_大中小划分 {


    public static void main(String[] args) {
        Judger.of(() -> {
                    int[] arr = RandomUtil.randomArray(RandomUtil.randomInt(1, 10), 0, 1000);
                    int pivot = arr[RandomUtil.randomInt(arr.length)];
                    Sout.println("pivot: ", pivot, arr);
                    new Q_数组三色_大中小划分().doit(arr, pivot);

                    test(arr, pivot);
                    return true;
                })
                .start().print();

    }

    static void doit(int[] arr, int pivot) {
        int le = 0, ri = arr.length - 1;
        for (int i = 0; i <= ri; i++) {
            if (arr[i] < pivot) {
                // 因为是从前往后看的, 不可能换来大的, 大的都会扔到后面去了, 不会换来小的, 因为小的都会在 le 前面, 只会是相等等的
                Tools.swap(arr, i, le);
                le++;
            } else if (arr[i] > pivot) {
                Tools.swap(arr, i, ri);
                ri--;
                // !! 换来的后面这个有可能会破坏, 需要将它当作刚遇到的值继续走一遍逻辑 !!
                i--;
                continue;
            } else {
                // 相等的, le, ri 指针不动
                continue;
            }
        }
    }

    static void test(int[] arr, int pivot) {
        boolean whiteStart = false;
        boolean whiteEnd = false;
        for (int i = 0; i < arr.length; i++) {
            if (whiteStart == false && arr[i] == pivot) {
                whiteStart = true;
            }
            if (whiteStart == true && arr[i] != pivot) {
                whiteEnd = true;
            }

            if (whiteStart == false) {
                Assert.isTrue(arr[i] < pivot);
            } else if (whiteEnd == false) {
                Assert.isTrue(arr[i] == pivot);
            } else {
                Assert.isTrue(arr[i] > pivot);
            }

        }
    }

}
